#include <iostream>

using namespace std;

// https://leetcode.cn/problems/path-sum/description/
// 112. 路径总和
// 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。
// 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
// 如果存在，返回 true ；否则，返回 false 。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0),left(nullptr),right(nullptr) {}
    TreeNode(int x): val(x),left(nullptr),right(nullptr) {}
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr)
            return false;
        if(root->left == nullptr && root->right == nullptr) // 判断是否是真正的叶子结点，终止条件为叶子结点
            return root->val == targetSum;  // 找到了路径

        if(hasPathSum(root->left, targetSum - root->val))
            return true;

        if(hasPathSum(root->right, targetSum - root->val))
            return true;

        return false;
    }
};

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
